Highest Product of 3 (Practice Interview Question)

You're out of free questions.

Given a list of integers, find the highest product you can get from three of the integers.

The input list_of_ints will always have at least three integers.

Gotchas

Does your function work with negative numbers? If list_of_ints is $[-10, -10, 1, 3, 2]$ we should return $300$ (which we get by taking $-10 * -10 * 3$ ).

We can do this in $O(n)$ time and $O(1)$ space.

Breakdown

To brute force ↴

A brute force algorithm finds a solution by trying all possible answers and picking the best one.

Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?

You could try running through all potential coin combinations and pick the one that adds to 67 cents using the fewest coins. That's a brute force algorithm, since you're trying all possible ways to make change.

Here are a few other brute force algorithms:

Trying to fit as many overlapping meetings as possible in a conference room? Run through all possible schedules, and pick the schedule that fits the most meetings in the room.
Trying to find the cheapest route through a set of cities? Try all possible routes and pick the cheapest one.
Looking for a minimum spanning tree in a graph? Try all possible sets of edges, and pick the cheapest set that's also a tree.

Brute force solutions are usually very slow since they involve testing a huge number of possible answers.

Brute force approaches are rarely the most efficient. Other approaches, like greedy algorithms or dynamic programming tend to be faster.

Even so, talking through a brute force solution can be a good first step in a coding interview. It's usually pretty easy to derive, so it allows you to quickly make progress and come up with something that works. From there, you have some helpful boundaries for refining your algorithm—you're only interested in solutions that are faster (and/or more space efficient) than the brute force solution you've already come up with.

an answer we could iterate through list_of_ints and multiply each integer by each other integer, and then multiply that product by each other other integer. This would probably involve nesting 3 loops. But that would be an

O(n^3)

runtime! We can definitely do better than that.

Because any integer in the list could potentially be part of the greatest product of three integers, we must at least look at each integer. So we're doomed to spend at least $O(n)$ time.

Sorting the list would let us grab the highest numbers quickly, so it might be a good first step. Sorting takes $O(n\lg{n})$ time. That's better than the $O(n^3)$ time our brute force approach required, but we can still do better.

Since we know we must spend at least $O(n)$ time, let's see if we can solve it in exactly $O(n)$ time.

A great way to get $O(n)$ runtime is to use a greedy ↴

A greedy algorithm builds up a solution by choosing the option that looks the best at every step.

Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?

Whenever picking which coin to use, you'd take the highest-value coin you could. A quarter, another quarter, then a dime, a nickel, and finally two pennies. That's a greedy algorithm, because you're always greedily choosing the coin that covers the biggest portion of the remaining amount.

Some other places where a greedy algorithm gets you the best solution:

Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.
Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.

Careful: sometimes a greedy algorithm doesn't give you an optimal solution:

When filling a duffel bag with cakes of different weights and values, choosing the cake with the highest value per pound doesn't always produce the best haul.
To find the cheapest route visiting a set of cities, choosing to visit the cheapest city you haven't been to yet doesn't produce the cheapest overall itinerary.

Validating that a greedy strategy always gets the best answer is tricky. Either prove that the answer produced by the greedy algorithm is as good as an optimal answer, or run through a rigorous set of test cases to convince your interviewer (and yourself) that its correct.

approach. How can we keep track of the highest_product_of_3 "so far" as we do one walk through the list?

Put differently, for each new current number during our iteration, how do we know if it gives us a new highest_product_of_3?

We have a new highest_product_of_3 if the current number times two other numbers gives a product that's higher than our current highest_product_of_3. What must we keep track of at each step so that we know if the current number times two other numbers gives us a new highest_product_of_3?

Our first guess might be:

our current highest_product_of_3
the three_numbers_which_give_highest_product

But consider this example:

  list_of_ints = [1, 10, -5, 1, -100]

Right before we hit $-100$ (so, in our second-to-last iteration), our highest_product_of_3 was $10$ , and the three_numbers_which_give_highest_product were $[10,1,1]$ . But once we hit $-100$ , suddenly we can take $-100 * -5 * 10$ to get $5000$ . So we should have "held on to" that $-5$ , even though it wasn't one of the three_numbers_which_give_highest_product.

We need something a little smarter than three_numbers_which_give_highest_product. What should we keep track of to make sure we can handle a case like this?

There are at least two great answers:

Keep track of the highest_2 and lowest_2 (most negative) numbers. If the current number times some combination of those is higher than the current highest_product_of_3, we have a new highest_product_of_3!
Keep track of the highest_product_of_2 and lowest_product_of_2 (could be a low negative number). If the current number times one of those is higher than the current highest_product_of_3, we have a new highest_product_of_3!

We'll go with (2). It ends up being slightly cleaner than (1), though they both work just fine.

How do we keep track of the highest_product_of_2 and lowest_product_of_2 at each iteration? (Hint: we may need to also keep track of something else.)

We also keep track of the lowest number and highest number. If the current number times the current highest—or the current lowest, if current is negative—is greater than the current highest_product_of_2, we have a new highest_product_of_2. Same for lowest_product_of_2.

So at each iteration we're keeping track of and updating:

highest_product_of_3
highest_product_of_2
highest
lowest_product_of_2
lowest

Can you implement this in code? Careful—make sure you update each of these variables in the right order, otherwise you might end up e.g. multiplying the current number by itself to get a new highest_product_of_2.

Solution

We use a greedy ↴

A greedy algorithm builds up a solution by choosing the option that looks the best at every step.

Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?

Some other places where a greedy algorithm gets you the best solution:

Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.
Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.

Careful: sometimes a greedy algorithm doesn't give you an optimal solution:

When filling a duffel bag with cakes of different weights and values, choosing the cake with the highest value per pound doesn't always produce the best haul.
To find the cheapest route visiting a set of cities, choosing to visit the cheapest city you haven't been to yet doesn't produce the cheapest overall itinerary.

approach to solve the problem in one pass. At each iteration we keep track of:

highest_product_of_3
highest_product_of_2
highest
lowest_product_of_2
lowest

When we reach the end, the highest_product_of_3 is our answer. We maintain the others because they're necessary for keeping the highest_product_of_3 up to date as we walk through the list. At each iteration, the highest_product_of_3 is the highest of:

the current highest_product_of_3
current * highest_product_of_2
current * lowest_product_of_2 (if current and lowest_product_of_2 are both low negative numbers, this product is a high positive number).

  def highest_product_of_3(list_of_ints):

    if len(list_of_ints) < 3:
        raise ValueError('Less than 3 items!')

    # We're going to start at the 3rd item (at index 2)
    # so pre-populate highests and lowests based on the first 2 items.
    # We could also start these as None and check below if they're set
    # but this is arguably cleaner
    highest = max(list_of_ints[0], list_of_ints[1])
    lowest  = min(list_of_ints[0], list_of_ints[1])
    highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
    lowest_product_of_2  = list_of_ints[0] * list_of_ints[1]

    # Except this one--we pre-populate it for the first *3* items.
    # This means in our first pass it'll check against itself, which is fine.
    highest_product_of_3 = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]

    # Walk through items, starting at index 2
    for i in range(2, len(list_of_ints)):
        current = list_of_ints[i]

        # Do we have a new highest product of 3?
        # It's either the current highest,
        # or the current times the highest product of two
        # or the current times the lowest product of two
        highest_product_of_3 = max(highest_product_of_3,
                                   current * highest_product_of_2,
                                   current * lowest_product_of_2)

        # Do we have a new highest product of two?
        highest_product_of_2 = max(highest_product_of_2,
                                   current * highest,
                                   current * lowest)

        # Do we have a new lowest product of two?
        lowest_product_of_2 = min(lowest_product_of_2,
                                  current * highest,
                                  current * lowest)

        # Do we have a new highest?
        highest = max(highest, current)

        # Do we have a new lowest?
        lowest = min(lowest, current)

    return highest_product_of_3

Complexity

$O(n)$ time and $O(1)$ additional space.

Bonus

What if we wanted the highest product of 4 items?
What if we wanted the highest product of $k$ items?
If our highest product is really big, it could
overflow. ↴
When you create an integer variable, your computer allocates a fixed number of bits for storing it. Most modern computers use 32 or 64 bits. But some numbers are so big they don't fit even in 64 bits, like sextillion (a billion trillion), which is 70 digits in binary.

Sometimes we might have a number that does fit in 32 or 64 bits, but if we add to it (or multiply it by something, or do another operation) the result might not fit in the original 32 or 64 bits. This is called an integer overflow.

For example, let's say we have just 2 bits to store integers with. So we can only hold the unsigned (non-negative) integers 0-3 in binary:

00 (0) 01 (1) 10 (2) 11 (3)

What happens if we have 3 (11) and we try to add 1 (01)? The answer is 4 (100) but that requires 3 bits and we only have 2.

What happens next depends on the language:

Some languages, like Python or Ruby, will notice that the result won't fit and automatically allocate space for a larger number.

In other languages, like C or Java, the processor will sort of "do its best" with the bits it has, taking the true result and throwing out any bits that don't fit. So in our example above, when adding 01 to 11, the processor would take the true result 100 and throw out the highest bit, leaving 00.

Swift will throw an error if an integer overflows, unless you've explicitly indicated that overflowing integers should be truncated to fit (like in C or Java).

In languages where integer overflow can occur, you can reduce its likelihood by using larger integer types, like C's long long int or Java's long. If you need to store something even bigger, there are libraries built to handle arbitrarily large numbers.

In some languages, you can also take advantage of overflow-checking features provided by the compiler or interpreter.
How should we protect against this?

What We Learned

Greedy ↴

A greedy algorithm builds up a solution by choosing the option that looks the best at every step.

Say you're a cashier and need to give someone 67 cents (US) using as few coins as possible. How would you do it?

Some other places where a greedy algorithm gets you the best solution:

Trying to fit as many overlapping meetings as possible in a conference room? At each step, schedule the meeting that ends earliest.
Looking for a minimum spanning tree in a graph? At each step, greedily pick the cheapest edge that reaches a new vertex.

Careful: sometimes a greedy algorithm doesn't give you an optimal solution:

When filling a duffel bag with cakes of different weights and values, choosing the cake with the highest value per pound doesn't always produce the best haul.
To find the cheapest route visiting a set of cities, choosing to visit the cheapest city you haven't been to yet doesn't produce the cheapest overall itinerary.

algorithms in action again!

That's not a coincidence—to illustrate how one pattern can be used to break down several different questions, we're showing this one pattern in action on several different questions.

Usually it takes seeing an algorithmic idea from a few different angles for it to really make intuitive sense.

Our goal here is to teach you the right way of thinking to be able to break down problems you haven't seen before. Greedy algorithm design is a big part of that way of thinking.

For this one, we built up our greedy algorithm exactly the same way we did for the Apple stocks question. By asking ourselves:

"Suppose we could come up with the answer in one pass through the input, by simply updating the 'best answer so far' as we went. What additional values would we need to keep updated as we looked at each item in our set, in order to be able to update the 'best answer so far' in constant time?"

For the Apple stocks question, the only "additional value" we needed was the min price so far.

For this one, we needed four things in order to calculate the new highest_product_of_3 at each step:

highest_product_of_2
highest
lowest_product_of_2
lowest

Do you have an answer?

Show answer

I have an answer Tell me more

Wanna review this one again later? Or do you feel like you got it all?

Mark as done Pin for review later

You're out of free questions.

Gotchas

Breakdown

Solution

Complexity

Bonus

What We Learned

Programming interview questions by company:

Programming interview questions by topic: